package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-15 11:07:35
 */
class Q0069_Sqrtx {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int mySqrt(int x) {
            if (x == 0 || x == 1) return x;

            long l = 0;
            long m = x >> 1;
            long r = x;

            while (l < m && m < r) {
                if (m * m > x) {
                    r = m;
                } else if (m * m < x) {
                    l = m;
                } else {
                    return (int) m;
                }

                m = l + ((r - l) >> 1);
            }
            return (int) m;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0069_Sqrtx().new Solution();
        System.out.println(solution.mySqrt(4));
        System.out.println(solution.mySqrt(8));
        System.out.println(solution.mySqrt(100));
        System.out.println(solution.mySqrt(Integer.MAX_VALUE));
        System.out.println(solution.mySqrt(2147395599));
        System.out.println(Integer.MAX_VALUE);
    }
}